package list;

public class LeetCode61 {
    /**
     * 利用查找倒数第k个节点完成
     * 并非最优
     */
    static class Find {
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || head.next == null || k == 0) {
                return head;
            }

            ListNode last = head;
            int size = 1;
            while (last.next != null) {
                last = last.next;
                size++;
            }

            if (k >= size) {
                k %= size;
            }

            if (k == 0) {
                return head;
            }

            ListNode x = find(head, k + 1);
            ListNode newHead = x.next;
            x.next = null;
            last.next = head;

            return newHead;
        }

        public ListNode find(ListNode head, int k) {
            ListNode p = head;
            ListNode p1 = head;
            while (p != null) {
                if (k <= 0) {
                    p1 = p1.next;
                }
                p = p.next;
                k--;
            }
            return p1;
        }
    }

    /**
     * 将链表闭合为环, 最后在合适的地方断开即可
     */
    static class circle {
        public ListNode rotateRight(ListNode head, int k) {

            if (head == null || head.next == null || k == 0) {
                return head;
            }

            ListNode last = head;
            int size = 1;
            while (last.next != null) {
                last = last.next;
                size++;
            }
            int add = size - k % size;
            if (add == size) {
                return head;
            }
            last.next = head;

            while (add-- > 0) {
                last = last.next;
            }
            ListNode newHead = last.next;
            last.next = null;
            return newHead;
        }
    }
}
